문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 쇼어 알고리즘 (문단 편집) === 양자 회로 구현 방법 === 먼저, 주기성을 가지는 이산 지수 함수의 형태인 이산 로그 문제 [math(f(x) = a^x \operatorname{mod}N )][* 참고로 [[RSA 암호화]]는 위 식을 기반으로 정보를 암호화한다.]을 살펴보자. 이 함수에서 [math(\frac{Q}{r} \ge N)]일때 [math(2N^2 \le Q \le 4N^2 )]를 만족하는 q의 비트값을 찾아야한다. 여기서 입력과 출력 큐비트 레지스터는 [math(Q-1)]과 0사이의 중첩값을 구축해야하기 때문이다. 여기서 x는 주기(r)이다. 양자 중첩을 구축하기 위해 [[레지스터]]를 다음과 같이 초기화 시켜야 한다. 레지스터는 이산 푸리에 변환(DFT) 형식의 식이다. || {{{#!wiki style="text-align: center" [math(\displaystyle \begin{aligned} \dfrac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x\rangle=\left(\displaystyle\dfrac{1}{\sqrt{2}}\sum_{x_\text{1}=0}^{1}|x_\text{1}\rangle\right) \otimes …. \otimes \left(\displaystyle\dfrac{1}{\sqrt{2}}\sum_{x_\text{q}=0}^{1}|x_\text{q}\rangle\right) \end{aligned})]}}} || 여기서 Q의 초기 상태는 중첩이고 1,0의 상태가 서로 중첩된 독립적인 큐비트를 쉽게 얻게된다. 이를 구현하려면 큐비트를 0의 위치로 초기화 한다음, [math(Q=2^q)]가 각 큐비트로 평행이 되게 하는 [[아다마르 변환#s-3.1|아다마르 게이트]]를 적용해야한다. 이제 위의 이산 지수 함수 [math(f(x))]를 양자 함수로 가정하고 양자 상태 함수로 다음과 같이 표현해보자. {{{#!wiki style="text-align: center" [math(U_\text{f}|x,0^q\rangle=|x,f(x)\rangle)]}}} 위의 단계를 양자함수에 넣어보자, 큐비트가 중첩 상태로 초기화함으로써 다음과 같은 식을 얻을수 있다. {{{#!wiki style="text-align: center" [math(\displaystyle\dfrac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x,0^q\rangle=\dfrac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x,f(x)\rangle)]}}} 이 식을 보면 알겠지만 Q의 상태는 아직 중첩이다. 하지만 이 식은 [math(q+n)]개의 큐비트들이 서로 얽혀 별개의 큐비트 상태 텐서곱으로 쓰일수없다. 따라서, 주기를 비롯한 여러 값의 큐비트를 한꺼번에 이용해야하므로, 입력 값을 제어하는 융합 게이트가 제어 큐비트를 변환해, 입력 큐비트인 x의 위상에 제어 큐비트가 저장된다. 이제 [math(Q=2^q)]라는 상태의 중첩을 제어해야한다. 양자 중첩을 제어하려면 확률적인 [math(|y\rangle)]상태에서 [math(|x\rangle)]의 진폭을 분리해야하는데, 주기성을 가진 임의의 양에서 진폭을 가진 주기 함수로 변환시키는 푸리에 변환을 입력 레지스터에 대입하면 된다. 단 중첩을 제어하는 상태의 범위가 이산적이므로, 연속적 푸리에 변환대신 [[DFT]]를 입력 레지스터에 적용하는 방식으로 원소가 각각 다른 x에 대한 다른 연산 방법을 산출하게 한다. {{{#!wiki style="text-align: center" [math(\displaystyle U_\text{IQFT}(|x\rangle)=\dfrac{1}{\sqrt{Q}}\sum_{y=0}^{Q-1}ω^{xy}|y\rangle)]}}} 이 식은 종결 상태로 유도한다. 중첩을 유도하기 위해 식을 다음으로 확장한다. {{{#!wiki style="text-align: center" [math(\displaystyle\dfrac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1}ω^{xy}|y,f(x)\rangle)]}}} {{{#!wiki style="text-align: center" [math(\displaystyle\dfrac{1}{Q}\sum_{z=0}^{N-1}\sum_{y=0}^{Q-1}\left(\displaystyle\sum_{x\in\mathbb {0,..,Q-1};f(x)=z}ω^{xy}\right)|y,z\rangle)]}}} 이제 각 변수를 다음과 같이 가정해보자 * Q번째 드무아브르 수를 [math(ω=e^{\frac{2\pi i}{Q}})]. * [math(f)]의 주기를 [math(r)]. * [math(x_\text{0})]는 양자함수 [math(z)]에 적용되는 [math(x\in\mathbb {0,..,Q-1})]에서 가장 작은 상태. * m-1은 [math(\left\lfloor \dfrac{Q-x_\text{0}-1}{r}\right\rfloor)] * 0부터 m-1까지 x의 인덱스를 b. 이 가정을 적용하면 복소 평면에서 [math(ω^{ry})]는 단위 벡터이므로 종결 상태에서[math(\frac{1}{Q}|y,z\rangle)]의 계수는 다음과 같이 나타내진다. || {{{#!wiki style="text-align: center" [math(\displaystyle \begin{aligned} \sum_{y=0}^{Q-1}\left(\displaystyle\sum_{x\in\mathbb {0,..,Q-1};f(x)=z}\right)ω^{xy}=\sum_{b=0}^{m-1}ω^{(x_\text{0}+rb)y}=ω^{x_\text{0}y}\sum_{b=0}^{m-1}ω^{rby} \end{aligned})]}}} || 그러므로, 복소평면에서 같은 방향에 가까운 단위 벡터 [math(ω^{rby})] 지점[* [math(ω^{ry})] 지점이 양수 실수축을 범위로 정하는]에서 양자 간섭이 발생한다. 입력 레지스터에서 y에 대한 결과들과 출력 레지스터에서 z에 대한 결과를 얻기 위해 [math(|y,z\rangle)]의 확률을 상기하면, || {{{#!wiki style="text-align: center" [math(\begin{aligned} P(|y,z\rangle)=\displaystyle|\dfrac{1}{Q}\sum_{x\in\mathbb {0,..,Q-1};f(x)=z}ω^{xy}|^2 \end{aligned})]}}} || 조건에 따라, 확률로 표현된 [math(|y,z\rangle)]의 계수를 정리하면 || {{{#!wiki style="text-align: center" [math(\displaystyle \begin{aligned} \dfrac{1}{Q^2}|\sum_{b=0}^{m-1}ω^{x_\text{0}y+rby}|^2 = \dfrac{1}{Q^2}|ω^{x_\text{0}y}|^2|\sum_{b=0}^{m-1}ω^{rby}|^2 =\dfrac{1}{Q^2}|\sum_{b=0}^{m-1}ω^{rby}|^2 \end{aligned})]}}} || {{{#!wiki style="text-align: center" [math(\displaystyle \dfrac{1}{Q^2}|\dfrac{ω^{mry}-1}{ω^{ry} - 1}|^2=\dfrac{1}{Q^2}\dfrac{\operatorname{sin}^2(\frac{\pi mry}{Q})}{\operatorname{sin}^2(\frac{\pi ry}{Q})})]}}} 이제 분석을 하면 이 확률이 높아지고 단위 벡터가 양수 실수축에 더 가까워지거나 혹은 [math(\frac{yr}{Q})]가 정수에 가까워짐을 보여준다. r^2가 아닌이상 이 확률은 Q의 원소가 되지 않는다. [math(\frac{yr}{Q})]이 어떤 정수 c에 가까워질수록, [math(\frac{y}{Q})]도 알려지지 않은 [math(\frac{c}{r})]에 가까워진다. 그러므로 [math(\frac{y}{Q})]에 고전적인 CFE을 사용해서 두가지 조건을 만족하는 [math(\frac{d}{s})]의 예상값을 찾아야 한다. 이 조건들이 주어졌을때 s는 적합한 주기 r이 될 가능성이 높거나 최소한 Q의 원소가 될수 있다. 이제 고전적 구현을 이용하여 [math(f(x)=f(x+s) ⇔ a^s = 1\,mod\,N)]을 확인한다. 위의 과정이 맞으면 종료한다. 그렇지 않으면 s와의 곱을 이용하여 r의 예상값을 찾거나[math(\frac{d}{s})]로 [math(\frac{y}{Q})]의 주변에 있는 다른 s값을 찾아본다. 다음 방법도 맞지 않을 경우 입력 레지스터를 초기화했는지부터 다시 한번 확인해본다. 여기에 대한 또다른 설명은 [[https://qiskit.org/textbook/ch-algorithms/shor.html|이 문서]]를 참고할 수 있다. [* [[https://qiskit.org/textbook/ch-algorithms/shor.html|Shor's Algorithm in Qiskit Textbook]]]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기